何謂 氣泡排序（Bubble Sort）

氣泡排序屬於初等排序的其中一種，假設 input 資料共 N 筆存放於 Array[0, 1, ....., (n-1)] 中，則每回合由左而右兩兩比較，若前者比後者大，則進行 swap，做到 index = n - i - 1 結束。每回合結束後，串列中最大值會上升到最高位置，最多做 (n - 1) 回合，若某回合中沒有任何 swap 動作，則代表已完成排序，可直接離開。

Demo

給予：6, 5, 7, 3, 4，(N = 5) 進行 bubble sort：

i = 0

Array[0] = 6, Array[1] = 5，交換。
Array[1] = 6, Array[2] = 7，不用交換。
Array[2] = 7, Array[3] = 3，交換。
Array[3] = 7, Array[4] = 4，交換。
Array = [5, 6, 3, 4, 7]，此時 7 為最大氣泡，上升至最高位置 Array[n - i - 1] = Array[4]

i = 1

Array[0] = 5, Array[1] = 6，不用交換。
Array[1] = 6, Array[2] = 3，交換。
Array[2] = 6, Array[3] = 4，交換。
Array = [5, 3, 4, 6, 7]，此時 6 為最大氣泡，上升至最高位置 Array[n - i - 1] = Array[3]

i = 2

Array[0] = 5, Array[1] = 3，交換。
Array[1] = 5, Array[2] = 4，交換。
Array = [3, 4, 5, 6, 7]，此時 5 為最大氣泡，上升至最高位置 Array[n - i - 1] = Array[2]

i = 3

Array[0] = 3, Array[1] = 4，不用交換。
Array = [3, 4, 5, 6, 7]，此時 4 為最大氣泡，上升至最高位置 Array[n - i - 1] = Array[1]

本次並無任何 SWAP，完成排序。

code

void swap(int arr[], int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
void bubbleSort(int arr[], int n){
    for(int i = 0; i < n - 1; i++){
        int flag = 0;
        for(int j = 0; j < n - i - 1; j++){
            if(arr[j + 1] < arr[j]){
                swap(arr, j, j + 1);
                flag = 1;
            }        
        }
        if(flag == 0){
            //No swap occur!
            break;
        }
    }
}

Time Complexity

1. Best case: O(n)
   發生於資料由小排到大的情況，代表只需做第一回合，執行 N - 1 次比較，即可跳出迴圈，完成排序。
   遞迴時間函數 T(n) = (n - 1) + 0 = (n - 1) = O(n)
2. Worst case: O(n^2)
   發生於資料由大到小的情況，代表每回合需要做 (n - i - 1) 次的 SWAP，i 從初值 0 做到 n - 2，因此總共的 SWAP 次數為：(n - 1) + (n - 2) + (n - 3) + ...... + 1 = n(n - 1) / 2 = O(n^2)
   遞迴時間函數 T(n) = (n - 1) + T(n - 1) = O(n^2)
3. Average case: O(n^2)
   遞迴時間函數 T(n) = 資料量 n 的平均 SWAP 次數 + T(n - 1)
   資料量 n 的平均 SWAP 次數為：(1 + 2 + 3 + 4 + 5 + 6 + ...... + (n - 1)) / (n - 1) = n / 2 = cn, c > 0
   因此遞迴時間函數 T(n) = cn + T(n - 1) = O(n^2)

stable sorting method

假設 input data = [5(前), 5(後)]
從程式碼來看，因為5(前) 並沒有大於 5(後)，因此 5(前) 必定出現在 5(後)之前，為 stable sorting method